package com.str.graphs;

import com.str.PQ.PriorityQueue;
import com.str.tree.UFTree;

public class Kruskal {

  private static class ElemE implements Comparable {
  	int v1;
  	int v2;
  	int distance;
  	
  	ElemE(int i, int j, int d) {
  	  v1 = i;
  	  v2 = j;
  	  distance = d;
    }
    
  	public int compareTo(Object that) {
      ElemE other = (ElemE) that;
      return distance - other.distance;
    }
  }

  private static void addEdgetoMST(int v1, int v2) {
    System.out.println("Add edge " + v1 + " to " + v2);
  }
  
  public static void kruskal(Graph g, PriorityQueue heap) {  // Kruskal's MST algorithm
    ElemE temp;
    for (int i=0; i<g.n(); i++)  // Put the edges on the array
      for (int w = g.first(i); w < g.n(); w = g.next(i, w)) {
      	temp = new ElemE(i, w, g.weight(i, w));
      	heap.add(temp);
      }
    UFTree uf = new UFTree(g.n()); // Equivalence class array      
    int numMST = g.n();           // Initially n equiv classes
    while (numMST > 1) {          // Combine equiv classes
      temp = (ElemE) heap.removeMin();         // Get next cheapest edge
      int v = temp.v1;  
      int u = temp.v2;
      if (uf.differ(v, u)) {       // Combine equiv classes
        addEdgetoMST(v, u);      // Add this edge to MST
        numMST--;                // One less MST
      }
    }
  }
}
